module DominoBestMove
	
	INFINITY = 9999999
	
	def init_lookup_table(l)
	  puts "initializing n choose k!"
    @lookup_table = initialize_n_choose_k(l)
  end
  
	def find_best_move(players, target_player, h_size, aggressor = false, max_depth = 5)
	  @max_depth = max_depth
	  @aggressor = aggressor
		@target = target_player
		@player_list = players
		@minmax = target_player.dup
		@minmax.points = 0
		@minmax.pool.dominos += unknown_dominos # -- would be better to track unknown dominos thru player.
		
		$logger.debug "Finding Best Move target #{target_player.name}, opp_hand size #{h_size}, max depth #{max_depth}"
		t1 = Time.now
		b = best_move(@minmax, false, h_size, 0)
		t2 = Time.now
		puts "BEST MOVE DONE! Done! taking time #{t2 - t1} seconds"
		$logger.debug "BEST MOVE DONE! Done! taking time #{t2 - t1} seconds"
		b
	end
	
	def best_move(player, no_count_points, opp_hand_size, tree_depth)
		
		is_max = (player.name == @target.name)
		is_prev_max = is_prev_max?(player)
		
		board = player.board
		pool = player.pool
		
		if board.game_started?
			if ((sum = board.sum_ends) % InteractiveDominos::SCORER) == 0
			  $logger.debug "Adding #{board.sum_ends} points! is it max? #{is_prev_max} count the points? #{!no_count_points}\n"
				player.points = is_prev_max ? (player.points + sum) : (player.points - sum) unless no_count_points #is previous player max and did they score?
			end
		end
		
		#we still hand and pool, so we know if last player won....
		previous_won = is_max ? opp_hand_size == 0 : player.hand.empty?
		
		#debug
		if just_draw && previous_won && is_max
		  $logger.debug "THIS IS THE SITUATION I'VE BEEN LOOKING FOR!!!"
		  raise "STOP!!! WEIRD SITUATION!"
		end
		
		if previous_won
			
			$logger.debug "THERE HAS BEEN A WINNER!!! is it max? #{is_prev_max}"
			
			sum=0
			if is_prev_max
				sum = fast_sum(pool, opp_hand_size)
				player.points = player.points + sum
			else
				sum = player.hand.sum
				player.points = player.points - sum
			end
			
			$logger.debug "points from opps hand #{sum}\n"
			
			player.name = player.name + "--LOSER--"
			return player
		end
		
		if tree_depth > @max_depth
		  $logger.debug "Board Depth too DEEP for #{player.name} points #{player.points}"
		  #we should adjust for hand size here, similar to how we handle the end of the game.
		  
		  #Feature TBA sum of hands:
		  max_hand = player.hand.sum
		  min_hand_approx = fast_sum(pool, opp_hand_size)
		  #player.points = player.points - max_hand + min_hand_approx
		  
		  #Feature TBA weighted valids
		  
		  #Feature NEEDED add expected best possible score!
		  #$logger.debug "Adjusted points is #{player.points} max_hand: #{max_hand}, min_hand_approx #{min_hand_approx}\n"
		  $logger.debug "Returning #{player.points} max_hand: #{max_hand}, min_hand_approx #{min_hand_approx}\n"
      return player
    end
		
		valids = if is_max
					player.legal_plays
				else
					pool.legal_plays(board)
				end
		
		print_debug(player, is_max, opp_hand_size, tree_depth)
		
		#black list can't remove them (make prob 0) it must reduce the probability to that of drawing it! (what is that?)
		#valids = remove_black_listed(valids, player, is_max, opp_hand_size == pool.size)
		
		if valids.empty?
			
			if is_max	#max has nothing to play.
				if pool.empty? #pool is empty count the points but have a hand
					
					$logger.debug "pool is empty for #{player.name} -- cumulate the points and return\n"
					
					sum = player.hand.sum.round_to_five
					player.points = player.points - sum
				elsif opp_hand_size >= pool.size #pool not empty but it's in opponents hand
				  
				  #i guess we gotta pass, right?
				  $logger.debug "#{player.name} is PASSING what will this mean?"
				  return best_move(change_name(player.dup), true, opp_hand_size, tree_depth+1)
				  
				else #we draw and assume we get the worst -- there is hand and pool but no play.
					
					$logger.debug "It's Time to DRAW!!!"
					
					#Change this so we only try the drawing when we near the end of the game (pool is small) otherwise
					#we should just subtract the average pool value from our points and call it a day.
					
					min_points = INFINITY
					worst = player.dup
					avg_points = 0
					values = []
					pool_size = pool.dominos.size
					pool.dominos.each do |d|
						p = player.dup
						p.force_draw d
						
						$logger.debug "#{player.name} draws a #{d}\n"
						
						r = best_move(p.dup, true, opp_hand_size, tree_depth+1)
						
						#alter points because dominoes on black list are more likely to be drawn
						
						avg_points = avg_points + r.points
						values << r.points
					end
					avg_points = avg_points / pool_size
					
					$logger.debug "AVG POINTS DETERMINED TO BE for #{player.name} average_points: #{avg_points} values #{values}\n"
					
					worst.points = avg_points
					return worst
				end
			else		#min has nothing to play. count the points. Count the pool because they must draw them in the end."
				sum = pool.sum.round_to_five
				player.points = player.points + sum
				
				$logger.debug "pool is empty for #{player.name} -- cumulate the points and return -- returning #{player.points} points\n"
			
			end
			return player
		end
		
		depends = is_max ? -1 : 1
		best = player.dup
		best.points = depends * INFINITY
		last = nil
		
		values = []
		
		valids.each do |k, v|
			
			v.each do |d|
				p = player.dup #use duplicate player state
				
				$logger.debug "#{p.name} gonna play #{k.to_s} on #{d.to_s} last played was the #{p.last_played.to_s}\n"
				
				p.play_domino k.dup, d, !is_max		#if it's not is_max pass the bypass flag to play from pool
				opp_hand_size_new = is_max ? opp_hand_size : opp_hand_size - 1
				r = best_move(change_name(p.dup), false, opp_hand_size_new, tree_depth+1)
				
				if is_max
					if r.points > best.points
						best = p
						best.points = r.points
					end
				else
				  #TODO
				  #alter points because black listed MUST be drawn by min (cannot be in hand)
          #cannot be valid for max AND be on black list
				  values << r.points
				end
			end
		end
		
		unless is_max
		  best.points = weighted_average(values, player, opp_hand_size, tree_depth)
		end
		
		if is_max
		  $logger.debug "BEST POINTS FOR #{player.name} DETERMINED TO BE" 
		  print_debug(best, is_max, opp_hand_size, tree_depth)
		else
		  $logger.debug "WEIGHTED AVG POINTS FOR #{player.name} DETERNUBED TO BE #{best.points}\n"
		end
		return best
	end
	
	#just switch the name to the next player in line. That way we can keep the board state in one player
	def change_name(player)
		i = @player_list.index{|p| p.name == player.name}
		new_name = @player_list[(i + 1) % @player_list.size].name
		player.name = new_name
		player
	end
	
	def unknown_dominos
		uns = []
		@player_list.each do |pl|
			uns << pl.dominos unless pl == @target
		end
		uns.flatten
	end
	
	def is_prev_max?(player)
		i = @player_list.index{|p| p.name == player.name}
		@player_list[i-1].name == @target.name
	end
	
	def print_debug(player, is_max, opp_hand_size, tree_depth)
		
		hand,valids = nil
		if !is_max
			hand = player.pool.dominos
			valids = player.pool.legal_plays(player.board)
		else
			hand = player.hand
			valids = player.legal_plays
		end
	
	  $logger.debug "Name: #{player.name}, hand #{hand.to_s}, last played #{player.last_played.to_s}, Points #{player.points} opp hand size #{opp_hand_size}"
	  $logger.debug "Valid plays: #{valids.to_s} DEPTH #{tree_depth}" 
    
    player.board.print_board
    player.pool.print_pool
    $logger.debug"\n"
	
	end
	
  def weighted_average(vals, player, h_size, td)
    
    #TODO
    #When we implement black list, we will need to adjust things They have different probabilty of being in the hand.
    
    p_size = player.pool.size
    nCk = @lookup_table[p_size][h_size]
    default_value = 0
    $logger.debug "calculating chance with vals #{vals}, player #{player.name}, hand size #{h_size}, depth #{td}"
    
    if vals.size + h_size < p_size #there is a chance we have no valids, we must consider that
      
      pl = player.dup
      
      #fill in extra space with max best move
      
      #black list all dominoes on the valids list
      valids_not_in_hand = pl.pool.legal_plays(pl.board).keys
      pl.board.update_black_list valids_not_in_hand
      
      $logger.debug "!!Considering points when #{player.name} cannot play:::hand size #{h_size}, vals size #{vals.size}, vals #{valids_not_in_hand} black list #{pl.board.black_list}"
      b = best_move(change_name(pl), true, h_size, td+1)
      default_value = b.points
    end
    
    vals = vals.sort #opponent favors plays with less points
    
    w_sum = 0
    num_sum = 0
    i = 1
    while p_size - i >= 0
      numerator = @lookup_table[p_size - i][h_size - 1]
      value = vals[i-1] || default_value
      w_sum = w_sum + value.to_f * (numerator.to_f/nCk.to_f)
      i = i + 1
      numerator = @lookup_table[p_size - i][h_size - 1] || 0
    end
    $logger.debug "calculated weighted average: p_size #{p_size}, vals_size: #{vals.size}, h_size: #{h_size}, nck: #{nCk}, values #{vals}, default value: #{default_value}, w_sum: #{w_sum}"
    w_sum
  end
  
  def fast_sum(vals, size)
    
    num_sets_in = @lookup_table[vals.size - 1][size - 1]
    num_sets = @lookup_table[vals.size][size]
  
    t_sum = vals.dominos.inject(0){|memo, v| memo + (v.value * num_sets_in)}
    (num_sets == 0) ? 0 : t_sum / num_sets
  end

  def initialize_n_choose_k(limit)
    b = (1..limit+1).inject(0){|memo, i|  memo + i}
    puts "limits: #{b}"
    
    lookup_table = []
    #initialize
    (0..b).each {|n| lookup_table[n] = [1]}
    (1..b).each {|k| lookup_table[0][k] = 0}
    
    (1..b).each do |n|
      (1..b).each do |k|
        lookup_table[n][k] = lookup_table[n-1][k-1] + lookup_table[n-1][k]
      end
    end
    lookup_table
  end
  
  def remove_black_listed(vals, player, is_max, endgame)
    if is_max
      vals
    else
      #just return vals if we are in endgame (opp_hand size == pool size)
      vals
    end
  end
end